#leetcode题目21：合并两个有序链表
#难度：简单
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：
from typing import List
class ListNode:
    def __init__(self, data):
        self.val = data
        self.next = None
#TODO 链表类，注意在leetcode中没有这个，纯粹是acm模式下才需要这个
class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        if not data:
            return None
        
        # 创建头结点
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        
        # 逐个为 data 内的数据创建结点,建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printlist(self, head):
        if head == None:
            return
        node = head
        while node != None:
            print(node.val, end=' ')
            node = node.next
        print()  # 换行






class Solution:
    def merge(self, head1, head2):
        dummy = ListNode(0)
        cur = dummy
        while head1 and head2:
            if head1.val <head2.val:
                cur.next = head1
                head1 = head1.next
            else:
                cur.next = head2
                head2 = head2.next
            cur = cur.next
        cur.next = head1 or head2
        return dummy.next


#测试数据
list_str1 = [1,2,4]
list_str2 = [1,3,4]
#预期输出：[1,1,2,3,4,4]
head1 = LinkList().initList(list_str1)
head2 = LinkList().initList(list_str2)
solution = Solution()
LinkList().printlist(solution.merge(head1,head2))
